<!DOCTYPE html>
<html lang="en">

<!-- Head tag -->
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="google-site-verification" content="xBT4GhYoi5qRD5tr338pgPM5OWHHIDR6mNg1a3euekI" />
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <meta name="description" content="">
    <meta name="keyword"  content="">
    <link rel="shortcut icon" href="/img/logo.png">
    <!-- Place this tag in your head or just before your close body tag. -->
    <script async defer src="https://buttons.github.io/buttons.js"></script>
    <title>
        
          对于动态规划的思考 - 宋正兵的博客 | zbsong Blog
        
    </title>

    <link rel="canonical" href="zbsong.top/article/算法—对动态规划的思考/">

    <!-- Bootstrap Core CSS -->
    <link rel="stylesheet" href="/css/bootstrap.min.css">

    <!-- Custom CSS --> 
    <link rel="stylesheet" href="/css/beantech.min.css">

    <link rel="stylesheet" href="/css/donate.css">
    
    <!-- Pygments Highlight CSS -->
    <link rel="stylesheet" href="/css/highlight.css">

    <link rel="stylesheet" href="/css/widget.css">

    <link rel="stylesheet" href="/css/rocket.css">

    <link rel="stylesheet" href="/css/signature.css">

    <link rel="stylesheet" href="/css/toc.css">

    <!-- Custom Fonts -->
    <!-- <link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.3.0/css/font-awesome.min.css" rel="stylesheet" type="text/css"> -->
    <!-- Hux change font-awesome CDN to qiniu -->
    <link href="https://cdn.staticfile.org/font-awesome/4.5.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">


    <!-- Hux Delete, sad but pending in China
    <link href='http://fonts.googleapis.com/css?family=Lora:400,700,400italic,700italic' rel='stylesheet' type='text/css'>
    <link href='http://fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800' rel='stylesheet' type='text/
    css'>
    -->


    <!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
    <!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
    <!--[if lt IE 9]>
        <script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
        <script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
    <![endif]-->

    <!-- ga & ba script hoook -->
    <script></script>
</head>


<!-- hack iOS CSS :active style -->
<body ontouchstart="">
	<!-- Modified by Yu-Hsuan Yen -->
<!-- Post Header -->
<style type="text/css">
    header.intro-header{
        
            background-image: url('https://api.dujin.org/bing/1920.php')
            /*post*/
        
    }
    
</style>

<header class="intro-header" >
    <!-- Signature -->
    <div id="signature">
        <div class="container">
            <div class="row">
                <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
                
                    <div class="post-heading">
                        <div class="tags">
                            
                              <a class="tag" href="/tags/#algorithm" title="algorithm">algorithm</a>
                            
                        </div>
                        <h1>对于动态规划的思考</h1>
                        <!-- <h2 class="subheading">记录关于动态规划的想法</h2> -->
                        <span class="meta">
                            宋正兵 on
                            2021-04-20
                        </span>
                    </div>
                


                </div>
            </div>
        </div>
    </div>
</header>

    <!-- Navigation -->
<nav class="navbar navbar-default navbar-custom navbar-fixed-top">
    <div class="container-fluid">
        <!-- Brand and toggle get grouped for better mobile display -->
        <div class="navbar-header page-scroll">
            <button type="button" class="navbar-toggle">
                <span class="sr-only">Toggle navigation</span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </button>
            <a class="navbar-brand" href="/">songzblink</a>
        </div>

        <!-- Collect the nav links, forms, and other content for toggling -->
        <!-- Known Issue, found by Hux:
            <nav>'s height woule be hold on by its content.
            so, when navbar scale out, the <nav> will cover tags.
            also mask any touch event of tags, unfortunately.
        -->
        <div id="huxblog_navbar">
            <div class="navbar-collapse">
                <ul class="nav navbar-nav navbar-right">
                    <li>
                        <a href="/">主页</a>
                    </li>
					<li>
                        <a href="/archive/">归档</a>
                    </li>
					<li>
                        <a href="/tags/">标签</a>
                    </li>
					<li>
                        <a href="/about/">关于</a>
                    </li>
					<!--
					修改about在前面的问题
                    
                        
                    
                        
                        <li>
                            <a href="/about/">关于</a>
                        </li>
                        
                    
                        
                        <li>
                            <a href="/archive/">归档</a>
                        </li>
                        
                    
                        
                        <li>
                            <a href="/tags/">标签</a>
                        </li>
                        
                    
                    -->
                </ul>
            </div>
        </div>
        <!-- /.navbar-collapse -->
    </div>
    <!-- /.container -->
</nav>
<script>
    // Drop Bootstarp low-performance Navbar
    // Use customize navbar with high-quality material design animation
    // in high-perf jank-free CSS3 implementation
    var $body   = document.body;
	// querySelector 获取文档中 id="demo" 的元素
    var $toggle = document.querySelector('.navbar-toggle');
    var $navbar = document.querySelector('#huxblog_navbar');
    var $collapse = document.querySelector('.navbar-collapse');

    $toggle.addEventListener('click', handleMagic)
    function handleMagic(e){
        if ($navbar.className.indexOf('in') > 0) {
        // CLOSE
            $navbar.className = " ";
            // wait until animation end.
            setTimeout(function(){
                // prevent frequently toggle
                if($navbar.className.indexOf('in') < 0) {
                    $collapse.style.height = "0px"
                }
            },400)
        }else{
        // OPEN
            $collapse.style.height = "auto"
            $navbar.className += " in";
        }
    }
</script>


    <!-- Main Content -->
    <!-- Modify by Yu-Hsuan Yen -->

<!-- Post Content -->
<article>
    <div class="container">
        <div class="row">

            <!-- Post Container -->
            <div class="
                col-lg-8 col-lg-offset-2
                col-md-10 col-md-offset-1
                post-container">

				
                <blockquote>
<p>这篇博客打算记录我在遇到动态规划题目时的一些思考。</p>
</blockquote>
<h2 id="1-最大子序和">1 最大子序和</h2>
<p><a href="https://leetcode-cn.com/problems/maximum-subarray/" target="_blank" rel="noopener">最大子序和</a></p>
<p>题目大意：给定一个整数数组 <code>nums</code> ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p>
<blockquote>
<p>因为之前做过这道题，但是脑子里还留有的印象只有定义一个变量 <code>sum</code> 一直累加，当 <code>sum &lt; 0</code> 的时候就令 <code>sum = 0</code>，同时记录最大值，但是对该问题没有一个清晰的思考，回寝室路上同 JCWang 讨论这道理颇受启发，故记录下来思考过程。</p>
</blockquote>
<h3 id="思考过程">思考过程</h3>
<p>首先看题目我们能有一个直觉是：利用动态规划一定能做！那么如何去定义 <strong>状态变量</strong> 呢？</p>
<p>我们首先需要知道，**【动态规划】的核心是让我们可以从最简单的情况开始考虑，通过逐步递推，每一步都能记住当前问题的答案，然后得到最终问题的答案。**这是一种【自底向上】思考问题的思路。</p>
<p>它不同于【记忆化递归】，记忆化递归是直接面对问题的求解，遇到一个问题后，通过缓存的方式将该问题的答案记录下来，下次遇到相同问题的时候从缓存中直接拿出答案。</p>
<p>回到这道题目本身，思考一个问题，我们的状态变量应该是设置为从第 i 个元素开始的最大和还是以第 i 个元素结尾的最大和呢？</p>
<p>如果选择“从第 i 个元素开始的最大子序和”，在最坏的情况下，遍历每一个开始元素都会一直执行到数组末尾。时间复杂度高不说，对于前一个状态 <code>dp[i - 1]</code> 也用不上来，这就谈不上是动态规划。</p>
<p>选择“以第 i 个元素结尾的最大子序和”，我们可以利用前一个状态 <code>dp[i - 1]</code> 来推断当前求得的和是否是最大和，来更新 <code>dp[i]</code>，即 <code>dp[i] = max(dp[i - 1] + nums[i], nums[i])</code>。</p>
<blockquote>
<p>递推式的获得取决于你对状态变量的定义，通过状态变量的定义观察当前状态和上一个状态的关系来确定你的递推式。</p>
</blockquote>
<p>好了，现在我们确定递推式为 <code>dp[i] = max(dp[i-1] + nums[i], nums[i])</code>，根据该递推式遍历完整个数组后，状态变量数组中最大的即我们要的答案。</p>
<h3 id="代码">代码</h3>
<p>代码如下：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxSubArray</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> n = nums.length;</span><br><span class="line">        <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];        </span><br><span class="line">        <span class="keyword">int</span> max = nums[<span class="number">0</span>];</span><br><span class="line">        dp[<span class="number">0</span>] = nums[<span class="number">0</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</span><br><span class="line">            dp[i] = Math.max(dp[i - <span class="number">1</span>] + nums[i], nums[i]);</span><br><span class="line">            <span class="comment">// 遍历的同时更新状态变量的最大值</span></span><br><span class="line">            <span class="keyword">if</span> (dp[i] &gt; max) &#123;</span><br><span class="line">                max = dp[i];</span><br><span class="line">            &#125;            </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> max;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="优化空间复杂度">优化空间复杂度</h3>
<p>分析上述过程，我们发现当前状态 <code>dp[i]</code> 之和上一个状态 <code>dp[i - 1]</code> 有关，于是我们可以只用一个变量 <code>sum</code> 来维护对于当前的 <code>dp[i]</code> 来讲，<code>dp[i - 1]</code> 应该是多少，从而让空间复杂度降低到 $O(1)$，类似于【滚动数组】的思想。</p>
<p>代码如下：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">maxSubArray</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> n = nums.length;</span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>, max = nums[<span class="number">0</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">            sum = Math.max(sum + nums[i], nums[i]);</span><br><span class="line">            max = Math.max(max, sum);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> max;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-扩展阅读三种遍历子串或者子序列的方式">2 扩展阅读——三种遍历子串或者子序列的方式</h2>
<p><strong>示例: [a, b , c, d , e]</strong></p>
<p>通常我们遍历子串或者子序列有三种遍历方式</p>
<ul>
<li>以某个节点为开头的所有子序列：如 [a]，[a, b]，[ a, b, c] … 再从以 b 为开头的子序列开始遍历 [b] [b, c]。</li>
<li>根据子序列的长度为标杆，如先遍历出子序列长度为 1 的子序列，在遍历出长度为 2 的等等。</li>
<li>以子序列的结束节点为基准，先遍历出以某个节点为结束的所有子序列，因为每个节点都可能会是子序列的结束节点，因此要遍历下整个序列，如：以 b 为结束点的所有子序列: [a , b] [b] 以 c 为结束点的所有子序列: [a, b, c] [b, c] [ c ]。</li>
</ul>
<p>第一种遍历方式通常用于暴力解法， 第二种遍历方式 leetcode (5. 最长回文子串 ) 中的解法就用到了。</p>
<p>第三种遍历方式因为可以产生递推关系，采用动态规划时，经常通过此种遍历方式，如背包问题，最大公共子串，这里的动态规划解法也是以先遍历出以某个节点为结束节点的所有子序列的思路</p>
<blockquote>
<p>作者：lao-hu-8<br>
链接：<a href="https://leetcode-cn.com/problems/maximum-subarray/solution/xiang-xi-jie-du-dong-tai-gui-hua-de-shi-xian-yi-li/" target="_blank" rel="noopener">https://leetcode-cn.com/problems/maximum-subarray/solution/xiang-xi-jie-du-dong-tai-gui-hua-de-shi-xian-yi-li/</a><br>
来源：力扣（LeetCode）<br>
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。</p>
</blockquote>
<h2 id="3-解码方法">3 解码方法</h2>
<p><a href="https://leetcode-cn.com/problems/decode-ways/" target="_blank" rel="noopener">解码方法</a></p>
<p>题目大意：一条包含字母 A-Z 的消息通过以下映射进行了 <strong>编码</strong> ：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">&apos;A&apos; -&gt; 1</span><br><span class="line">&apos;B&apos; -&gt; 2</span><br><span class="line">...</span><br><span class="line">&apos;Z&apos; -&gt; 26</span><br></pre></td></tr></table></figure>
<p>要 <strong>解码</strong> 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。给你一个只含数字的 <strong>非空</strong> 字符串 <code>s</code> ，请计算并返回 <strong>解码</strong> 方法的 <strong>总数</strong> 。</p>
<h3 id="思路1-递归">思路1 递归</h3>
<p>把解码字符串的过程看作是一棵树，对于每个节点我们都有 <strong>单独解码</strong> 或者 <strong>联合解码</strong> 两种选择去生成该节点的子节点。</p>
<ul>
<li>退出条件：
<ul>
<li>搜索完最后一个字符：表示找到了一种解码方法，返回 <code>1</code>；</li>
<li>当前子串的第一个字符为 <code>0</code>：当前解码方法走不下去了，返回 <code>0</code>;</li>
</ul>
</li>
<li>单独解码：如果第 <code>i</code> 位字符大于 <code>0</code>，那么一定能够单独解码，下一次解码从第 <code>i+1</code> 位开始;</li>
<li>联合解码：如果第 <code>i</code> 位字符和第 <code>i-1</code> 位字符组成的数字在 <code>[10,26]</code> 之内就可以进行联合解码；</li>
<li>如果同时单独解码和联合解码，那么 <code>解码方法的总数 = 单独解码 + 联合解码</code>。</li>
</ul>
<p>代码：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numDecodings</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> n = s.length();</span><br><span class="line">        <span class="keyword">if</span> (n == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">1</span>; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">char</span> ch = s.charAt(<span class="number">0</span>);</span><br><span class="line">        <span class="keyword">if</span> (ch == <span class="string">'0'</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 一棵树的形式，一层一层的往下解码，每个节点都有单独自己解码和联合下一个字符解码两种选择</span></span><br><span class="line">        <span class="comment">// 当前字字符不为'0'，必定能自己单独解码</span></span><br><span class="line">        <span class="keyword">int</span> count = numDecodings(s.substring(<span class="number">1</span>));</span><br><span class="line">        <span class="comment">// 判断是否能和下一个字符联合解码</span></span><br><span class="line">        <span class="keyword">if</span> (n &gt; <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (ch == <span class="string">'1'</span> || (ch == <span class="string">'2'</span> &amp;&amp; s.charAt(<span class="number">1</span>) &lt;= <span class="string">'6'</span>)) &#123;</span><br><span class="line">                count += numDecodings(s.substring(<span class="number">2</span>));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> count;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>很显然，它会超时。</p>
<h3 id="思路2-优化递归记忆化搜索">思路2 优化递归，记忆化搜索</h3>
<p>分析递归的代码，发现我们重复计算了多次 <code>numDecodings(s[index,n])</code>，<code>s[index,n]</code> 是字符串 <code>s</code> 的子串，<code>n</code>是 <code>s</code> 的长度。那么我们可以开辟一块内存空间来存储计算的结果，下次遇到相同的计算直接返回。</p>
<p>代码：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 记忆化搜索</span></span><br><span class="line">    <span class="keyword">int</span>[] buffer;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numDecodings</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">char</span>[] arr = s.toCharArray();</span><br><span class="line">        buffer = <span class="keyword">new</span> <span class="keyword">int</span>[arr.length];</span><br><span class="line">        <span class="keyword">return</span> decodings(arr, <span class="number">0</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">decodings</span><span class="params">(<span class="keyword">char</span>[] arr, <span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (index == arr.length) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 搜索缓存</span></span><br><span class="line">        <span class="keyword">if</span> (buffer[index] != <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> buffer[index];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (arr[index] == <span class="string">'0'</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 一棵树的形式，一层一层的往下解码，每个节点都有单独自己解码和联合下一个字符解码两种选择</span></span><br><span class="line">        <span class="comment">// 当前字字符不为'0'，必定能自己单独解码</span></span><br><span class="line">        <span class="keyword">int</span> count = decodings(arr, index + <span class="number">1</span>);</span><br><span class="line">        <span class="comment">// 判断是否能和下一个字符联合解码</span></span><br><span class="line">        <span class="keyword">if</span> (arr.length - index &gt; <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (arr[index] == <span class="string">'1'</span> || (arr[index] == <span class="string">'2'</span> &amp;&amp; arr[index + <span class="number">1</span>] &lt;= <span class="string">'6'</span>)) &#123;</span><br><span class="line">                count += decodings(arr, index + <span class="number">2</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 存入缓存</span></span><br><span class="line">        buffer[index] = count;</span><br><span class="line">        <span class="keyword">return</span> count;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这下不超时了，但是还能不能继续优化呢？</p>
<h3 id="思路3-动态规划">思路3 动态规划</h3>
<blockquote>
<p>有些人啊，他就是吃饱了撑的。</p>
</blockquote>
<p>递归的方法时间复杂度确实高，那么就可以去考虑递推的解法。</p>
<p>前面有过分析，对于第 <code>i</code> 位字符，有两种选择，一种是自己单独解码，另外一种是联合第 <code>i+1</code> 位字符进行解码。但是我们是用递推诶！你联合第 <code>i+1</code> 位字符，我们的递推就是去推第 <code>i+1</code> 位的状态，所以我们把它换成是联合第 <code>i - 1</code> 位字符进行解码。（第 <code>i+1</code> 位也不是不行，只不过一个是从左往右递推，一个是从右往左递推罢了）</p>
<p>那么我们定义状态变量 <code>dp[i]</code> 表示前 <code>i</code> 位字符的解码方法的总数。对于第 <code>i</code> 位字符，有三种情况存在：</p>
<ul>
<li>只能自己单独解码</li>
<li>只能联合前一位字符解码</li>
<li>既能自己单独解码，又能联合前一位字符解码</li>
</ul>
<p>于是可以得到状态转移方程：</p>
<ul>
<li><code>dp[i] = dp[i - 1]</code>，只能自己单独解码；</li>
<li><code>dp[i] = dp[i - 2]</code>，只能联合前一位字符解码；</li>
<li><code>dp[i] = dp[i - 1] + dp[i - 2]</code>，既能自己单独解码，又能联合前一位字符解码</li>
</ul>
<p>代码：【细节】由于题目存在前导零，而前导零不能被解码，可以进行特判，也可以往字符串头部追加空格作为哨兵，追加空格既可以避免讨论前导零，也能使下标从 <code>1</code> 开始，简化 <code>dp[i-2]</code> 等负数下标的判断。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numDecodings</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">        s = <span class="string">" "</span> + s;</span><br><span class="line">        <span class="keyword">int</span> n = s.length();</span><br><span class="line">        <span class="keyword">char</span>[] arr = s.toCharArray();</span><br><span class="line">        <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">        dp[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</span><br><span class="line">            <span class="comment">// 独自编码[1,9]</span></span><br><span class="line">            <span class="keyword">if</span> (arr[i] &gt; <span class="string">'0'</span>) &#123;</span><br><span class="line">                dp[i] += dp[i - <span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 联合编码[10,26] || // 既能独自又能联合</span></span><br><span class="line">            <span class="keyword">if</span> (arr[i - <span class="number">1</span>] == <span class="string">'1'</span> || (arr[i - <span class="number">1</span>] == <span class="string">'2'</span> &amp;&amp; arr[i] &lt;= <span class="string">'6'</span>)) &#123;</span><br><span class="line">                dp[i] += dp[i - <span class="number">2</span>];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> dp[n - <span class="number">1</span>];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="思路4-空间优化">思路4 空间优化</h3>
<p>来了来了，随迟但到。对于 <code>dp[i]</code> 来讲，我们只用到了 <code>dp[i - 1]</code> 和 <code>dp[i - 2]</code>，所以我们只需要开辟一个长度为 <code>3</code> 的数组即可。通过取余的方式循环复用不需要的下标。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">numDecodings</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">        s = <span class="string">" "</span> + s;</span><br><span class="line">        <span class="keyword">int</span> n = s.length();</span><br><span class="line">        <span class="keyword">char</span>[] arr = s.toCharArray();</span><br><span class="line">        <span class="keyword">int</span>[] dp = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">3</span>];</span><br><span class="line">        dp[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</span><br><span class="line">            dp[i % <span class="number">3</span>] = <span class="number">0</span>;</span><br><span class="line">            <span class="comment">// 独自编码[1,9]</span></span><br><span class="line">            <span class="keyword">if</span> (arr[i] &gt; <span class="string">'0'</span>) &#123;</span><br><span class="line">                dp[i % <span class="number">3</span>] += dp[(i - <span class="number">1</span>) % <span class="number">3</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 联合编码[10,26] || // 既能独自又能联合</span></span><br><span class="line">            <span class="keyword">if</span> (arr[i - <span class="number">1</span>] == <span class="string">'1'</span> || (arr[i - <span class="number">1</span>] == <span class="string">'2'</span> &amp;&amp; arr[i] &lt;= <span class="string">'6'</span>)) &#123;</span><br><span class="line">                dp[i % <span class="number">3</span>] += dp[(i - <span class="number">2</span>) % <span class="number">3</span>];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> dp[(n - <span class="number">1</span>) % <span class="number">3</span>];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<blockquote>
<p>学习的时候啥都好讲，做题的时候能够写出来 AC 才是正道。</p>
</blockquote>

                
                <hr>
                <!-- Pager -->
                <ul class="pager">
                    
                        <li class="previous">
                            <a href="/article/项目—秒杀总结/" data-toggle="tooltip" data-placement="top" title="秒杀项目的总结">&larr; 上一篇</a>
                        </li>
                    
                    
                        <li class="next">
                            <a href="/article/算法—两数之和三数之和四数之和/" data-toggle="tooltip" data-placement="top" title="两数之和三数之和四数之和">下一篇 &rarr;</a>
                        </li>
                    
                </ul>

                <br>

                <!--打赏-->
                
                <!--打赏-->

                <br>
                <!--分享-->
                
                <!--分享-->
                <br>                       
                
                <!-- require APlayer -->
                
            </div>
            
            <!-- Tabe of Content -->
            <!-- Table of Contents -->

  
    <style>
      span.toc-nav-number{
        display: none
      }
    </style>
  
    
      <aside id="sidebar">
        <div id="toc" class="toc-article">
        <strong class="toc-title">目录</strong>
        
          <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#1-最大子序和"><span class="toc-nav-number">1.</span> <span class="toc-nav-text">1 &#x6700;&#x5927;&#x5B50;&#x5E8F;&#x548C;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#思考过程"><span class="toc-nav-number">1.1.</span> <span class="toc-nav-text">&#x601D;&#x8003;&#x8FC7;&#x7A0B;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#代码"><span class="toc-nav-number">1.2.</span> <span class="toc-nav-text">&#x4EE3;&#x7801;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#优化空间复杂度"><span class="toc-nav-number">1.3.</span> <span class="toc-nav-text">&#x4F18;&#x5316;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#2-扩展阅读三种遍历子串或者子序列的方式"><span class="toc-nav-number">2.</span> <span class="toc-nav-text">2 &#x6269;&#x5C55;&#x9605;&#x8BFB;&#x2014;&#x2014;&#x4E09;&#x79CD;&#x904D;&#x5386;&#x5B50;&#x4E32;&#x6216;&#x8005;&#x5B50;&#x5E8F;&#x5217;&#x7684;&#x65B9;&#x5F0F;</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#3-解码方法"><span class="toc-nav-number">3.</span> <span class="toc-nav-text">3 &#x89E3;&#x7801;&#x65B9;&#x6CD5;</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#思路1-递归"><span class="toc-nav-number">3.1.</span> <span class="toc-nav-text">&#x601D;&#x8DEF;1 &#x9012;&#x5F52;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#思路2-优化递归记忆化搜索"><span class="toc-nav-number">3.2.</span> <span class="toc-nav-text">&#x601D;&#x8DEF;2 &#x4F18;&#x5316;&#x9012;&#x5F52;&#xFF0C;&#x8BB0;&#x5FC6;&#x5316;&#x641C;&#x7D22;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#思路3-动态规划"><span class="toc-nav-number">3.3.</span> <span class="toc-nav-text">&#x601D;&#x8DEF;3 &#x52A8;&#x6001;&#x89C4;&#x5212;</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#思路4-空间优化"><span class="toc-nav-number">3.4.</span> <span class="toc-nav-text">&#x601D;&#x8DEF;4 &#x7A7A;&#x95F4;&#x4F18;&#x5316;</span></a></li></ol></li></ol>
        
        </div>
      </aside>
    

                
            <!-- Sidebar Container -->
            <div class="
                col-lg-8 col-lg-offset-2
                col-md-10 col-md-offset-1
                sidebar-container">

                <!-- Featured Tags -->
                
                <section>
                    <!-- no hr -->
                    <h5><a href="/tags/">标签</a></h5>
                    <div class="tags">
                       
                          <a class="tag" href="/tags/#algorithm" title="algorithm">algorithm</a>
                        
                    </div>
                </section>
                

                <!-- Friends Blog -->
				<!--
                
                <hr>
                <h5>朋友们</h5>
                <ul class="list-inline">

                    
                        <li><a href="https://tyzhang.top/" target="_blank">ztygalaxy</a></li>
                    
                        <li><a href="http://www.yctang.club/" target="_blank">yctang</a></li>
                    
                        <li><a href="https://dolnw.github.io" target="_blank">JCWang</a></li>
                    
                </ul>
                
				-->
            </div>
        </div>
    </div>
</article>


<!-- async load function -->
<script>
    function async(u, c) {
      var d = document, t = 'script',
          o = d.createElement(t),
          s = d.getElementsByTagName(t)[0];
      o.src = u;
      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
      s.parentNode.insertBefore(o, s);
    }
</script>
<!-- anchor-js, Doc:http://bryanbraun.github.io/anchorjs/ -->
<script>
    async("https://cdn.bootcss.com/anchor-js/1.1.1/anchor.min.js",function(){
        anchors.options = {
          visible: 'hover',
          placement: 'left',
          icon: ''
        };
        anchors.add().remove('.intro-header h1').remove('.subheading').remove('.sidebar-container h5');
    })
</script>
<style>
    /* place left on bigger screen */
    @media all and (min-width: 800px) {
        .anchorjs-link{
            position: absolute;
            left: -0.75em;
            font-size: 1.1em;
            margin-top : -0.1em;
        }
    }
</style>


<!-- chrome Firefox 中文锚点定位失效-->
<script src="https://cdn.bootcss.com/jquery/3.3.1/jquery.js"></script>
<!-- smooth scroll behavior polyfill  -->
<script type="text/javascript" src="/js/smoothscroll.js"></script>
<script>
        $('#toc').on('click','a',function(a){
            // var isChrome = window.navigator.userAgent.indexOf("Chrome") !== -1;
            // console.log(window.navigator.userAgent,isChrome)
                // if(isChrome) {
                    // console.log(a.currentTarget.outerHTML);
                    // console.log($(a.currentTarget).attr("href"));
                    //跳转到指定锚点
                    // document.getElementById(a.target.innerText.toLowerCase()).scrollIntoView(true);
                    document.getElementById($(a.currentTarget).attr("href").replace("#","")).scrollIntoView({behavior: 'smooth' });
                // }
        })  
</script>


    <!-- Footer -->
    <!-- Footer -->
<footer>
    <div class="container">
        <div class="row">
            <div class="col-lg-8 col-lg-offset-2 col-md-10 col-md-offset-1">
                <ul class="list-inline text-center">
                
                
                
				
                

                

                
                    <li>
                        <a target="_blank"  href="https://github.com/songzblink">
                            <span class="fa-stack fa-lg">
                                <i class="fa fa-circle fa-stack-2x"></i>
                                <i class="fa fa-github fa-stack-1x fa-inverse"></i>
                            </span>
                        </a>
                    </li>
                

                

                </ul>
                <p class="copyright text-muted">
                    Copyright &copy; 宋正兵 2021 
                    <br>
                    Theme by <a href="http://www.huweihuang.com">Huwei Huang</a>
                    re-Ported by <a href="https://github.com/ztygalaxy">ztygalaxy</a>
					
                </p>
            </div>
        </div>
    </div>
</footer>

<!-- jQuery -->
<script src="/js/jquery.min.js"></script>

<!-- Bootstrap Core JavaScript -->
<script src="/js/bootstrap.min.js"></script>

<!-- Custom Theme JavaScript -->
<script src="/js/hux-blog.min.js"></script>


<!-- async load function -->
<script>
    function async(u, c) {
      var d = document, t = 'script',
          o = d.createElement(t),
          s = d.getElementsByTagName(t)[0];
      o.src = u;
      if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
      s.parentNode.insertBefore(o, s);
    }
</script>

<!-- 
     Because of the native support for backtick-style fenced code blocks 
     right within the Markdown is landed in Github Pages, 
     From V1.6, There is no need for Highlight.js, 
     so Huxblog drops it officially.

     - https://github.com/blog/2100-github-pages-now-faster-and-simpler-with-jekyll-3-0  
     - https://help.github.com/articles/creating-and-highlighting-code-blocks/    
-->
<!--
    <script>
        async("http://cdn.bootcss.com/highlight.js/8.6/highlight.min.js", function(){
            hljs.initHighlightingOnLoad();
        })
    </script>
    <link href="http://cdn.bootcss.com/highlight.js/8.6/styles/github.min.css" rel="stylesheet">
-->


<!-- jquery.tagcloud.js -->
<script>
    // only load tagcloud.js in tag.html
    if($('#tag_cloud').length !== 0){
        async("zbsong.top/js/jquery.tagcloud.js",function(){
            $.fn.tagcloud.defaults = {
                //size: {start: 1, end: 1, unit: 'em'},
                color: {start: '#bbbbee', end: '#0085a1'},
            };
            $('#tag_cloud a').tagcloud();
        })
    }
</script>

<!--fastClick.js -->
<script>
    async("https://cdn.bootcss.com/fastclick/1.0.6/fastclick.min.js", function(){
        var $nav = document.querySelector("nav");
        if($nav) FastClick.attach($nav);
    })
</script>


<!-- Google Analytics -->




<!-- Baidu Tongji -->






	<a id="rocket" href="#top" class=""></a>
	<script type="text/javascript" src="/js/totop.js?v=1.0.0" async=""></script>
    <script type="text/javascript" src="/js/toc.js?v=1.0.0" async=""></script>
<!-- Image to hack wechat -->
<img src="zbsong.top/img/icon_wechat.png" width="0" height="0" />
<!-- Migrate from head to bottom, no longer block render and still work -->

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<!--
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
-->
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML"></script>
</body>

</html>
